package com.lw.leetcode.linked.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 6256. 将节点分成尽可能多的组
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/5 9:35
 */
public class MagnificentSets {

    public static void main(String[] args) {
        MagnificentSets test = new MagnificentSets();

        // 4
        int n = 6;
        int[][] edges = {{1, 2}, {1, 4}, {1, 5}, {2, 6}, {2, 3}, {4, 6}};

        // -1
//        int n = 3;
//        int[][] edges = {{1, 2}, {2, 3}, {3, 1}};

        // 57
//        int n = 92;
//        int[][] edges = {{67, 29}, {13, 29}, {77, 29}, {36, 29}, {82, 29}, {54, 29}, {57, 29},
//                {53, 29}, {68, 29}, {26, 29}, {21, 29}, {46, 29}, {41, 29}, {45, 29}, {56, 29},
//                {88, 29}, {2, 29}, {7, 29}, {5, 29}, {16, 29}, {37, 29}, {50, 29}, {79, 29},
//                {91, 29}, {48, 29}, {87, 29}, {25, 29}, {80, 29}, {71, 29}, {9, 29}, {78, 29},
//                {33, 29}, {4, 29}, {44, 29}, {72, 29}, {65, 29}, {61, 29}};

        int i = test.magnificentSets(n, edges);
        System.out.println(i);
    }

    public int magnificentSets(int n, int[][] edges) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            map.computeIfAbsent(a, v -> new ArrayList<>()).add(b);
            map.computeIfAbsent(b, v -> new ArrayList<>()).add(a);
        }
        int[] arr = new int[n + 1];

        int[] counts = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            long v = find(map, i, arr);
            if (v == -1) {
                return -1;
            }
            if (v == -2) {
                counts[i] = 1;
                continue;
            }
            int min = (int) (v >> 32);
            int step = (int) v;
            if (arr[min] > 0) {
                counts[i] = 0;
            } else {
                counts[min] = step;
            }
            counts[min] = Math.max(counts[min], step);
        }

        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += counts[i];
        }
        return sum;
    }

    private long find(Map<Integer, List<Integer>> map, int t, int[] arr) {
        LinkedList<Long> list = new LinkedList<>();
        list.add((long) t);
        int step = 0;
        Arrays.fill(arr, -1);
        arr[t] = 0;
        long min = t;
        while (!list.isEmpty()) {
            step++;
            int size = list.size();
            for (int i = 0; i < size; i++) {
                long pop = list.pop();
                int pre = (int) (pop >> 32);
                long item = pop & 0XFFFFFFFFL;
                List<Integer> li = map.get((int) item);
                if (li == null) {
                    return -2;
                }
                item <<= 32;
                for (int v : li) {
                    min = Math.min(min, v);
                    if (v == pre || arr[v] == step) {
                        continue;
                    }
                    if (arr[v] == -1) {
                        arr[v] = step;
                        list.add(item + v);
                    } else if (arr[v] != step - 2) {
                        return -1;
                    }
                }
            }
        }
        return (min << 32) + step;
    }

}
